package leetcode_700;

import helpclass.TreeNode;

/**
 *@author 周杨
 *MaximumBinaryTree_654 构造最大二叉树 最大二叉树就是根节点最大的二叉树
 *describe:先用动态规划 规划区间最大数组 然后递归构造二叉树 AC 3%(...)
 *2018年9月27日 下午2:02:29
 */
public class MaximumBinaryTree_654 {
	public TreeNode constructMaximumBinaryTree(int[] nums) {
        int dp[][]=new int[nums.length][nums.length];
        for(int i=0;i<nums.length;++i) {//构造dp数组
        	dp[i][i]=i;
        	for(int j=0;j<i;++j) {
        		if(nums[dp[j][i-1]]<nums[i])
        			dp[j][i]=i;
        		else
        			dp[j][i]=dp[j][i-1];
        	}
        }
        return help(0,nums.length-1,nums,dp);
	}
	
	private TreeNode help(int left,int right,int[]nums,int dp[][]) {
		if(left>right)
			return null;
		if(left==right)
			return new TreeNode(nums[left]);
		int maxIndex=dp[left][right];
		TreeNode root=new TreeNode(nums[maxIndex]);
		root.left=help(left,maxIndex-1,nums,dp);
		root.right=help(maxIndex+1,right,nums,dp);
		return root;
	}
}
